import math
import random
from random import *
import numpy as np
import matplotlib.pyplot as plt


# 初始化种群: 随机生成0、1序列(以列表形式)，二进制编码
def initialize_population():
    population = []
    for i in range(PopulationSize):
        individual = list(np.random.randint(0, 2, size=BinaryLength))
        population.append(individual)  # 使用np的随机数函数，快速生成0、1序列
    return population


# 解码: 将一个二进制串转为实数值
def decode(individual):
    tmp_list = [str(i) for i in individual]  # 列表中元素转化为字符
    tmp_str = ''.join(tmp_list)  # 列表转字符串
    value = Lx + int(tmp_str, 2) * ActualSearchAccuracy  # 二进制字符串转为十进制
    return value


# 计算种群的适应度,这里即函数值
def compute_fitness(population):
    fits = []  # 适应度集合
    for i in population:
        value = decode(i)  # 解码
        fx = 10 * math.sin(5 * value) + 7 * abs(value - 5) + 10  # 计算适应度
        fits.append(fx)
    return fits


# 选择: 赌轮选择 and 精英保存策略
def select(population):
    fits = compute_fitness(population)  # 计算种群每个个体的适应度
    best_one = population[fits.index(max(fits))].copy()  # 保存具有最高适应度的个体！！！！
    population.remove(best_one)  # 从去除最大、最小适应度个体的种群中选择
    fits.remove(max(fits))
    population.pop(fits.index(min(fits)))
    fits.remove(min(fits))
    population = choices(population, weights=fits, k=PopulationSize - 2)  # 快速实现赌轮选择
    return population, best_one  # 返回 N-2 个被选择的个体集合，以及最高适应度个体


# 交叉: 从去除最大、最小适应度的 N-2 个个体中进行交叉操作
def crossover(population):
    for i in range(0, len(population), 2):  # 每两个一组,进行交叉变异
        if random() < pc:  # 如果[0,1]之间的随机数小于pc，则对这两个个体进行交叉
            point = randint(1, BinaryLength)  # 一点交叉
            population[i][0:point], population[i + 1][point:BinaryLength] = \
                population[i + 1][0:point], population[i][point:BinaryLength]
    return population


# 变异: 对去除最大、最小适应度的 N-2 个个体中的每个个体进行变异操作
def mutation(population):
    for i in range(len(population)):
        for j in range(BinaryLength):
            if random() < pm:  # 如果[0,1]之间的随机数小于pm，则对该个体的该二进制串位置取反
                population[i][j] = (population[i][j] + 1) % 2  # 变异，0-1,1-0
    return population


# 求得当前种群中的最优解
def best(population):
    fits = compute_fitness(population)
    best_index = fits.index(max(fits))
    best_value = decode(population[best_index])
    return population[best_index], best_value, fits[best_index]  # 返回最优解二进制串、最优解实数值、最优解适应度


# 遗传算法
# GA 参数
Lx = 0      # x的下界
Ux = 10     # x的上界
pc = 0.6    # 交叉概率
pm = 0.005  # 变异概率
G = 100     # 迭代次数
PopulationSize = 100    # 初始群体规模
BinaryLength = 15       # 二进制编码长度
ActualSearchAccuracy = (Ux - Lx) / (2 ** BinaryLength - 1)  # 实际搜索精度
# 初始化种群
origin_population = initialize_population()
# 迭代 G 次
for k in range(G+1):
    # 选择操作: 保存最高适应度个体，从去除最大、最小适应度的 N-2 个个体中进行选择
    next_population, cur_best = select(origin_population)
    # 交叉操作: 对被选择的 N-2 个个体进行交叉操作
    next_population = crossover(next_population)
    # 变异操作: 再交叉过后的 N-2 个个体进行变异操作
    next_population = mutation(next_population)
    # 最高适应度个体复制两份，加入 N-2 个个体中，得到 N 规模种群
    next_population.append(cur_best)
    next_population.append(cur_best)
    shuffle(next_population)  # 随机打乱种群
    # 替换原种群
    origin_population = next_population.copy()
    # 每迭代10次画一张图，展示算法拟合效果
    if k % 20 == 0:
        x = np.arange(0, 10, 0.1)
        y = 10 * np.sin(5 * x) + 7 * abs(x - 5) + 10
        tmp_x = []
        for m in origin_population:
            tmp_x.append(decode(m))
        tmp_y = compute_fitness(origin_population)
        cx = np.array(tmp_x)
        cy = np.array(tmp_y)
        plt.plot(cx, cy, '*', color='g')
        plt.title(f"iterations = {k}")
        plt.plot(x, y)
        plt.show()
# 迭代结束，输出最优解
x = np.arange(0, 10, 0.1)
y = 10 * np.sin(5 * x) + 7 * abs(x - 5) + 10
plt.plot(x, y)
best_individual, best_x, best_y = best(origin_population)  # 求出当前种群的最优解
plt.scatter(best_x, best_y, marker='o', color='red')
plt.title("y = 10sin(5x) + 7|x-5| + 10")
plt.xlabel('x ∈ [0, 10]')
plt.ylabel('y')
print(f'The best x is {best_x}')
print(f'The best y is {best_y}')
plt.show()
